package HouseRobberIII;

import java.util.HashMap;

public class Solution {
    public int rob(TreeNode root) {
    	if (root==null) return 0;
    	HashMap<TreeNode,Integer> tdp0=new HashMap<>();
    	HashMap<TreeNode,Integer> tdp1=new HashMap<>();
        return(Math.max(tdp(root,0,tdp0,tdp1), tdp(root,1,tdp0,tdp1)));
    }

	private int tdp(TreeNode root, int i, HashMap<TreeNode, Integer> tdp0, HashMap<TreeNode, Integer> tdp1) {
		if (root.left==null&&root.right==null){
			if (i==1) return root.val;
			else return 0;
		}
		if ((i==0) && (tdp0.get(root)!=null)) return tdp0.get(root);
		if ((i==1) && (tdp1.get(root)!=null)) return tdp1.get(root);
			
		int max=0;
		if (i==1){
			max=root.val+Math.max(max, (root.left==null?0:tdp(root.left,0,tdp0,tdp1))+(root.right==null?0:tdp(root.right,0,tdp0,tdp1)));
			tdp1.put(root, max);
			
		}
		if (i==0){
			int maxLeft=0,maxRight=0;
			maxLeft=root.left==null?0:Math.max(tdp(root.left,0,tdp0,tdp1), tdp(root.left,1,tdp0,tdp1));
			maxRight=root.right==null?0:Math.max(tdp(root.right,0,tdp0,tdp1), tdp(root.right,1,tdp0,tdp1));
			max=maxLeft+maxRight;
			tdp0.put(root, max);
		}
		System.out.println(max);
		return max;
	}
	public static void main(String args[]) {
		int[] val={3,2,3,-1,3,-1,1};
		TreeNode[] tree=new TreeNode[val.length+1];
		for (int i=1;i<=val.length;i++)
			if(val[i-1]!=-1){
				TreeNode treeNode=new TreeNode(val[i-1]);
				tree[i]=treeNode;
				if (i!=1)
					if (i%2==0)
						tree[i/2].left=treeNode;
					else 
						tree[i/2].right=treeNode;
					
			}
		Solution so=new Solution();
		System.out.println(so.rob(tree[1]));
	}
}